# 排序链表: https://leetcode-cn.com/problems/sort-list/submissions
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        """
            按照题意， 往nlogn  时间复杂度上想， 就是用归并排序
        """

        if not head or not head.next:
            return head

        def mergeLinked(l1, l2):
            dumpy = ListNode()
            h = dumpy
            while l1 and l2:
                if l1.val > l2.val:
                    h.next = l2
                    l2 = l2.next
                    h = h.next
                else:
                    h.next = l1
                    l1 = l1.next
                    h = h.next
            
            if l1: h.next = l1
            if l2: h.next = l2

            head = dumpy.next
            # 删除首元结点
            # dumpy.next = None
            del dumpy
            return head
        
        def mergeSort(l):
            if not l.next:
                return l
            
            # 快慢指针，求中点
            low = fast = l
            while fast.next and fast.next.next:
                low = low.next
                fast = fast.next.next
            
            # 分成俩链表
            left = l
            right = low.next
            low.next = None
            # 求左右
            left = mergeSort(left)
            right = mergeSort(right)
            # 合并
            return mergeLinked(left, right)

        return mergeSort(head)


# 上面是自底向上的， 还有一种自顶向下的方法， 可以省去递归的开销， 空间复杂度只需要O(1), 时间复杂度不变

